BOJ17099 Contest

풀이

대회를 (s,e,c) tuple로 정렬해두고 “f(i) = [i,n)대회를 나갈 수 있을때 최대이득”이라고 정의하면 f(i)=max(f(i+1),f(j)+c[i]) where j=e[i]<s[k]인 k들 중에 최소 와 같은 점화식을 세울 수 있습니다. 상태전이를 위한 j는 정렬된 배열에서 이분탐색으로 찾아줄 수 있으므로 O(NlogN)에 문제를 풀 수 있습니다. http://boj.kr/87d565a9aefd47ea859cf06179202915